package com.leetcode.array;

import java.util.*;

/**
 * 两个数组的交集 II
 * 给定两个数组，编写一个函数来计算它们的交集。
 * 示例 1：
 * 输入：nums1 = [1,2,2,1], nums2 = [2,2]
 * 输出：[2,2]
 * 示例 2:
 * 输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
 * 输出：[4,9]
 * 说明：
 * 输出结果中每个元素出现的次数，应与元素在两个数组中出现次数的最小值一致。
 * 我们可以不考虑输出结果的顺序。
 * 进阶：
 * 如果给定的数组已经排好序呢？你将如何优化你的算法？
 * 如果nums1的大小比nums2小很多，哪种方法更优？
 * 如果nums2的元素存储在磁盘上，内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？
 *
 * 作者：力扣 (LeetCode)
 * 链接：https://leetcode-cn.com/leetbook/read/top-interview-questions/xmcbym/
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 */
class Code350 {
    public static void main(String[] args) {
        int[] nums1 = {2,2};
        int[] nums2 = {1,2,3,1};
        int[] rs = intersect1(nums1,nums2);
        for(int num :rs){
            System.out.print(num);
            System.out.print(",");
        }
    }
    public static int[] intersect1(int[] nums1, int[] nums2) {
        Map<Integer,Integer> map = new HashMap<Integer, Integer>();
        int[] arr = new int[nums1.length];
        for(int num : nums1){
            if(map.containsKey(num)){
                map.put(num, map.get(num)+1);
            }else{
                map.put(num, 0);
            }
        }
        int index = 0;
        for(int num : nums2){
            if(map.containsKey(num)){
                arr[index++] = num;
                if(map.get(num) >= 1){
                    map.put(num, map.get(num)-1);
                }else{
                    map.remove(num);
                }
            }
        }
        return Arrays.copyOfRange(arr, 0, index);
    }
}
